Skip to content

Day 10:二维叉积、线段求交与共线重叠 ​

学习方向:线性代数 + 计算机图形学 + CAD 开发

编程语言:TypeScript

核心主题:二维叉积、方向判断、平行与共线、参数方程、线段求交、重叠区间、退化线段


一、学习目标 ​

本节在 Day 09 向量投影和点到线段距离的基础上,学习二维几何中另一个非常重要的算法:线段与线段的相交检测。

主要解决以下问题:

  1. 什么是二维叉积?
  2. 叉积与点积有什么区别?
  3. 如何利用叉积判断两个向量的方向关系?
  4. 如何判断两条直线是否平行?
  5. 如何判断两条直线是否共线?
  6. 如何使用参数方程表示线段?
  7. 如何推导两条直线的交点参数 t、u?
  8. 如何判断交点是否位于有限线段上?
  9. 如何处理共线线段的重叠?
  10. 如何处理线段端点接触?
  11. 如何处理零长度线段?
  12. 如何使用 TypeScript 实现完整的 intersectSegments()?

完成标准 ​

  • [ ] 理解二维叉积的计算公式。
  • [ ] 能根据叉积正负判断方向。
  • [ ] 能区分平行与共线。
  • [ ] 理解线段参数方程。
  • [ ] 能推导交点参数 t、u。
  • [ ] 能计算两条线段的交点。
  • [ ] 能判断交点是否位于有限线段内。
  • [ ] 能计算共线线段的重叠区间。
  • [ ] 能处理端点接触。
  • [ ] 能处理零长度线段。
  • [ ] 能实现 pointOnSegment()。
  • [ ] 能实现 intersectCollinearSegments()。
  • [ ] 能实现 intersectSegments()。

二、问题背景:CAD 为什么需要线段求交? ​

假设 CAD 中存在两条线段:

text
A ---------------- B
          |
          |
          |
          C
          |
          |
          D

两条线段存在一个交点。

CAD 需要计算:

  • 是否相交?
  • 交点坐标是多少?
  • 交点是否位于两条有限线段内?
  • 如果两条线段重叠,重叠部分是什么?
  • 如果只是端点接触,应该返回什么?
  • 如果某条线段长度为零,如何处理?

这些问题广泛应用于:

  1. CAD 交点吸附。
  2. 线段修剪(Trim)。
  3. 线段延长(Extend)。
  4. 图形碰撞检测。
  5. 多边形边界检测。
  6. 图形裁剪。
  7. 几何布尔运算。
  8. 施工图辅助绘制。

本节最终目标是实现:

typescript
function intersectSegments(
    A: Vector2,
    B: Vector2,
    C: Vector2,
    D: Vector2
): IntersectionResult

三、回顾向量点积(Dot Product) ​

Day 04、Day 05 和 Day 09 已经学习点积。

已知:

a=(ax,ay)b=(bx,by)

点积:

a⋅b=axbx+ayby

几何公式:

a⋅b=|a||b|cos⁡θ

点积主要用于:

  • 计算夹角。
  • 判断垂直。
  • 计算投影。
  • 计算最近点。
  • 计算线段参数。

TypeScript ​

typescript
type Vector2 = {
    x: number;
    y: number;
};

function dotProduct(
    a: Vector2,
    b: Vector2
): number {
    return a.x * b.x + a.y * b.y;
}

四、二维叉积(Cross Product) ​

4.1 什么是叉积? ​

对于二维向量:

a=(ax,ay)b=(bx,by)

定义二维叉积:

a×b=axby−aybx

与点积不同:

  • 点积使用加法。
  • 二维叉积使用减法。
  • 两者在二维情况下都返回一个标量。

4.2 TypeScript 实现 ​

typescript
function crossProduct(
    a: Vector2,
    b: Vector2
): number {
    return a.x * b.y - a.y * b.x;
}

4.3 计算示例 ​

已知:

a=(3,2)b=(1,4)

计算:

a×b=3×4−2×1a×b=12−2

得到:

a×b=10

4.4 二维叉积与三维叉积的关系 ​

严格来说,三维向量叉积的结果是向量。

将二维向量扩展到 XY 平面:

a=(ax,ay,0)b=(bx,by,0)

三维叉积:

a×b=[00axby−aybx]

二维叉积通常只保留 Z 分量:

cross2D(a,b)=axby−aybx

所以二维叉积返回标量。


五、叉积的几何意义 ​

5.1 叉积与方向 ​

在 Y 轴向上的数学坐标系中:

叉积结果几何意义
a×b>0从 a 到 b 逆时针转动
a×b<0从 a 到 b 顺时针转动
a×b=0两个向量平行,或存在零向量

5.2 叉积为正 ​

例如:

a=(1,0)b=(0,1)

计算:

a×b=1×1−0×0=1

因此:

a×b>0

表示从 a 到 b 逆时针旋转 90°。

5.3 叉积为负 ​

例如:

a=(1,0)b=(0,−1)

计算:

a×b=1×(−1)−0×0=−1

因此:

a×b<0

表示从 a 到 b 顺时针旋转 90°。

5.4 叉积为零 ​

例如:

a=(2,2)b=(4,4)

计算:

a×b=2×4−2×4=0

说明两个非零向量平行。

5.5 叉积与面积 ​

二维叉积的绝对值等于两个向量构成的平行四边形面积:

Area=|a×b|

例如:

a=(3,0)b=(0,4)

得到:

Area=|3×4|=12

由两个向量构成的三角形面积为:

Areatriangle=|a×b|2

这也是后续多边形面积计算的基础。


六、点积与叉积的区别 ​

对比项目点积二维叉积
公式axbx+aybyaxby−aybx
返回值标量标量
三角函数关系cos⁡θsin⁡θ
判断垂直适合不直接用于判断
判断平行不直接用于判断适合
计算投影适合不直接用于计算
判断方向可判断夹角锐钝可判断左右转向
CAD 应用拾取、距离、投影相交、方向、共线

二维叉积还满足:

a×b=|a||b|sin⁡θ

这里的 θ 是从 a 到 b 的有向角。

注意:

如果使用浏览器中 Y 轴向下的屏幕坐标,叉积正负对应的视觉旋转方向会发生变化。


七、使用叉积判断点在线段的哪一侧 ​

已知三个点:

A, B, P

定义:

r=B−Aq=P−A

计算:

cross(r,q)

在 Y 轴向上的坐标系中:

  • 大于 0:P 位于有向直线 AB 左侧。
  • 小于 0:P 位于有向直线 AB 右侧。
  • 等于 0:A、B、P 共线,或者 AB 退化为点。

TypeScript ​

typescript
function subtractVector(
    a: Vector2,
    b: Vector2
): Vector2 {
    return {
        x: a.x - b.x,
        y: a.y - b.y
    };
}

function orientation(
    A: Vector2,
    B: Vector2,
    P: Vector2
): number {
    const AB = subtractVector(B, A);
    const AP = subtractVector(P, A);

    return crossProduct(AB, AP);
}

示例 ​

typescript
const A = { x: 0, y: 0 };
const B = { x: 10, y: 0 };

console.log(
    orientation(A, B, { x: 5, y: 5 })
);

// 50:左侧

console.log(
    orientation(A, B, { x: 5, y: -5 })
);

// -50:右侧

console.log(
    orientation(A, B, { x: 5, y: 0 })
);

// 0:共线

注意:

共线不代表点一定在线段内部。

例如:

A=(0,0),B=(10,0)P=(20,0)

三个点共线,但 P 不在线段 AB 上。


八、判断两条直线是否平行 ​

已知两条线段:

ABCD

定义方向向量:

r=B−As=D−C

如果:

r×s=0

则两个方向向量线性相关。

当 r、s 都不是零向量时,说明两条直线平行。

TypeScript ​

typescript
function areParallel(
    A: Vector2,
    B: Vector2,
    C: Vector2,
    D: Vector2
): boolean {
    const r = subtractVector(B, A);
    const s = subtractVector(D, C);

    const rr = dotProduct(r, r);
    const ss = dotProduct(s, s);

    if (rr === 0 || ss === 0) {
        return false;
    }

    return crossProduct(r, s) === 0;
}

这里约定:

零长度线段不参与普通直线的平行判断。

示例 ​

typescript
const A = { x: 0, y: 0 };
const B = { x: 10, y: 0 };

const C = { x: 0, y: 5 };
const D = { x: 10, y: 5 };

console.log(
    areParallel(A, B, C, D)
);

// true

九、平行与共线的区别 ​

这是 Day 10 的重点。

9.1 平行 ​

两条直线方向相同或相反,但不一定在同一条直线上。

例如:

text
A ---------------- B


C ---------------- D

9.2 共线 ​

两条线段位于同一条无限直线上。

例如:

text
A -------- C -------- B -------- D

9.3 共线判断公式 ​

定义:

r=B−As=D−Cq=C−A

如果:

r×s=0

并且:

q×r=0

在 AB、CD 都不是零长度线段的前提下,说明两条直线共线。

9.4 TypeScript ​

typescript
function areCollinear(
    A: Vector2,
    B: Vector2,
    C: Vector2,
    D: Vector2
): boolean {
    const r = subtractVector(B, A);
    const s = subtractVector(D, C);
    const q = subtractVector(C, A);

    if (
        dotProduct(r, r) === 0 ||
        dotProduct(s, s) === 0
    ) {
        return false;
    }

    return (
        crossProduct(r, s) === 0 &&
        crossProduct(q, r) === 0
    );
}

9.5 示例:平行但不共线 ​

A=(0,0)B=(10,0)C=(0,5)D=(10,5)

方向向量:

r=(10,0)s=(10,0)

计算:

r×s=0

但:

q=C−A=(0,5)q×r=0×0−5×10=−50

因此:

两条直线平行,但不共线。


十、线段的参数方程 ​

10.1 什么是参数方程? ​

已知线段:

A=(Ax,Ay)B=(Bx,By)

线段所在直线上的任意点可以表示为:

P(t)=A+t(B−A)

其中:

t∈R

10.2 参数 t 的几何意义 ​

t位置
t<0A 点外侧
t=0A 点
0<t<1AB 内部
t=1B 点
t>1B 点外侧

因此:

0≤t≤1

表示点位于有限线段 AB 上。

10.3 示例 ​

已知:

A=(0,0)B=(10,10)

参数方程:

P(t)=(0,0)+t(10,10)

当:

t=0.5

得到:

P=(5,5)

当:

t=1.5

得到:

P=(15,15)

此时点位于线段延长线上。

10.4 TypeScript ​

typescript
function pointAt(
    A: Vector2,
    B: Vector2,
    t: number
): Vector2 {
    return {
        x: A.x + (B.x - A.x) * t,
        y: A.y + (B.y - A.y) * t
    };
}

测试:

typescript
console.log(
    pointAt(
        { x: 0, y: 0 },
        { x: 10, y: 10 },
        0.5
    )
);

// { x: 5, y: 5 }

十一、两条直线的交点推导 ​

这是 Day 10 最重要的公式推导。

11.1 定义两条直线 ​

第一条:

P(t)=A+t(B−A)

第二条:

Q(u)=C+u(D−C)

定义:

r=B−As=D−Cq=C−A

那么:

P(t)=A+trQ(u)=C+us

11.2 相交条件 ​

如果两条直线相交,那么交点相同:

A+tr=C+us

整理:

tr−us=C−A

因此:

tr−us=q

现在有两个未知数:

t, u

目标是求出它们。

11.3 推导 t ​

原方程:

tr−us=q

两边与 s 做叉积:

(tr−us)×s=q×s

根据叉积的分配律:

t(r×s)−u(s×s)=q×s

因为:

s×s=0

所以:

t(r×s)=q×s

得到:

t=q×sr×s

11.4 推导 u ​

原方程:

tr−us=q

两边与 r 做叉积:

(tr−us)×r=q×r

展开:

t(r×r)−u(s×r)=q×r

因为:

r×r=0

并且:

s×r=−(r×s)

所以:

u(r×s)=q×r

得到:

u=q×rr×s

11.5 最终公式 ​

t=q×sr×su=q×rr×s

前提:

r×s≠0

也就是说,两条直线不能平行。


十二、判断两条有限线段是否相交 ​

求出 t、u 后:

如果:

0≤t≤1

并且:

0≤u≤1

那么两条有限线段相交。

否则:

两条无限直线虽然可能相交,但交点不在两条有限线段的公共范围内。

TypeScript 判断 ​

typescript
if (
    t < 0 || t > 1 ||
    u < 0 || u > 1
) {
    return { type: "none" };
}

如果满足范围:

typescript
const intersection = pointAt(A, B, t);

即可得到交点。


十三、普通线段相交示例 ​

已知:

A=(0,0)B=(10,10)C=(0,10)D=(10,0)

第一步:计算方向向量 ​

r=B−A=(10,10)s=D−C=(10,−10)q=C−A=(0,10)

第二步:计算分母 ​

r×s=10×(−10)−10×10r×s=−200

分母不为零,因此两条直线不平行。

第三步:计算 t ​

q×s=0×(−10)−10×10q×s=−100

所以:

t=−100−200=0.5

第四步:计算 u ​

q×r=0×10−10×10q×r=−100

所以:

u=−100−200=0.5

第五步:判断范围 ​

0≤0.5≤1

两者均满足。

因此两条线段相交。

第六步:计算交点 ​

P=A+trP=(0,0)+0.5(10,10)

得到:

P=(5,5)

十四、为什么不能只判断分母是否为零? ​

如果:

r×s=0

说明两条直线方向平行。

但是存在两种情况。

情况 1:平行但不共线 ​

text
A ---------------- B

C ---------------- D

结果:

typescript
{ type: "none" }

情况 2:共线 ​

text
A -------- C -------- B -------- D

此时可能:

  1. 完全分离。
  2. 端点接触。
  3. 部分重叠。
  4. 完全包含。
  5. 完全重合。

因此:

分母为零时,不能直接返回不相交。

必须进一步判断是否共线。


十五、共线线段的重叠问题 ​

15.1 示例 ​

已知:

A=(0,0)B=(10,10)C=(5,5)D=(15,15)

四个点位于同一条直线上。

排列关系:

text
A -------- C -------- B -------- D

因此重叠部分为:

text
C -------- B

即:

(5,5)→(10,10)

15.2 如何计算? ​

使用 Day 09 学习的向量投影。

将 C、D 投影到 AB 的参数轴上。


十六、共线线段的参数投影 ​

16.1 定义向量 ​

r=B−Aq=C−A

线段 AB 参数区间:

[0,1]

16.2 计算 C 的参数 ​

t0=(C−A)⋅rr⋅r

16.3 计算 D 的参数 ​

t1=(D−A)⋅rr⋅r

16.4 示例 ​

已知:

A=(0,0)B=(10,10)C=(5,5)D=(15,15)

首先:

r=(10,10)r⋅r=102+102=200

计算:

t0=(5,5)⋅(10,10)200t0=100200=0.5

计算:

t1=(15,15)⋅(10,10)200t1=300200=1.5

因此:

线段 AB:

[0,1]

线段 CD:

[0.5,1.5]

它们的交集:

[0.5,1]

十七、计算重叠区间 ​

17.1 为什么需要 min 和 max? ​

因为线段 CD 的端点顺序可能相反。

例如:

C=(15,15)D=(5,5)

那么:

t0=1.5t1=0.5

如果直接假设:

t0<t1

就可能得到错误结果。

因此需要先排序:

minT=min(t0,t1)maxT=max(t0,t1)

17.2 与 AB 区间求交 ​

AB 的参数区间:

[0,1]

CD 的参数区间:

[minT,maxT]

交集起点:

startT=max(0,minT)

交集终点:

endT=min(1,maxT)

合并写法:

startT=max(0,min(t0,t1))endT=min(1,max(t0,t1))

17.3 判断结果 ​

条件几何结果
startT>endT不相交
startT=endT端点接触
startT<endT存在重叠线段

17.4 计算重叠端点 ​

start=A+startT(B−A)end=A+endT(B−A)

TypeScript:

typescript
const start = pointAt(A, B, startT);
const end = pointAt(A, B, endT);

十八、设计线段求交返回类型 ​

线段求交可能存在三种结果:

  1. 不相交。
  2. 相交于一个点。
  3. 重叠一段线段。

因此不应该只返回:

typescript
boolean

更合理的方式是使用 TypeScript 联合类型。

18.1 IntersectionResult ​

typescript
type IntersectionResult =
    | {
        type: "none";
    }
    | {
        type: "point";
        point: Vector2;
    }
    | {
        type: "overlap";
        start: Vector2;
        end: Vector2;
    };

18.2 不相交 ​

typescript
{
    type: "none"
}

18.3 单点相交 ​

typescript
{
    type: "point",
    point: {
        x: 5,
        y: 5
    }
}

18.4 线段重叠 ​

typescript
{
    type: "overlap",
    start: {
        x: 5,
        y: 5
    },
    end: {
        x: 10,
        y: 10
    }
}

18.5 为什么使用联合类型? ​

因为不同相交情况需要不同的数据。

例如:

CAD 交点吸附:

typescript
if (result.type === "point") {
    // 使用 result.point
}

CAD 重叠检测:

typescript
if (result.type === "overlap") {
    // 使用 result.start 和 result.end
}

TypeScript 可以根据 type 自动缩小类型范围。


十九、实现 intersectCollinearSegments() ​

19.1 函数职责 ​

专门处理两条已经确认共线的非零长度线段。

需要:

  1. 计算 AB 的方向向量。
  2. 计算 C、D 在 AB 上的参数。
  3. 计算两个参数区间的交集。
  4. 判断是否分离。
  5. 判断是否端点接触。
  6. 返回重叠线段。

19.2 TypeScript 完整实现 ​

typescript
function intersectCollinearSegments(
    A: Vector2,
    B: Vector2,
    C: Vector2,
    D: Vector2
): IntersectionResult {
    // 1. 计算方向向量
    const r = subtractVector(B, A);
    const q = subtractVector(C, A);

    // 2. AB 长度平方
    const rr = dotProduct(r, r);

    // 3. 防止零长度线段
    if (rr === 0) {
        return { type: "none" };
    }

    // 4. 确保 C 位于 AB 所在直线上
    if (crossProduct(q, r) !== 0) {
        return { type: "none" };
    }

    // 5. C 在 AB 参数轴上的位置
    const t0 = dotProduct(q, r) / rr;

    // 6. D 在 AB 参数轴上的位置
    const t1 = dotProduct(
        subtractVector(D, A),
        r
    ) / rr;

    // 7. 求区间交集
    const startT = Math.max(
        0,
        Math.min(t0, t1)
    );

    const endT = Math.min(
        1,
        Math.max(t0, t1)
    );

    // 8. 不相交
    if (startT > endT) {
        return { type: "none" };
    }

    // 9. 只有一个公共点
    if (startT === endT) {
        return {
            type: "point",
            point: pointAt(A, B, startT)
        };
    }

    // 10. 存在重叠线段
    return {
        type: "overlap",
        start: pointAt(A, B, startT),
        end: pointAt(A, B, endT)
    };
}

19.3 示例:部分重叠 ​

typescript
const result = intersectCollinearSegments(
    { x: 0, y: 0 },
    { x: 10, y: 10 },
    { x: 5, y: 5 },
    { x: 15, y: 15 }
);

console.log(result);

预期:

typescript
{
    type: "overlap",
    start: { x: 5, y: 5 },
    end: { x: 10, y: 10 }
}

19.4 示例:完全分离 ​

typescript
const result = intersectCollinearSegments(
    { x: 0, y: 0 },
    { x: 5, y: 5 },
    { x: 8, y: 8 },
    { x: 12, y: 12 }
);

预期:

typescript
{
    type: "none"
}

19.5 示例:端点接触 ​

typescript
const result = intersectCollinearSegments(
    { x: 0, y: 0 },
    { x: 5, y: 5 },
    { x: 5, y: 5 },
    { x: 10, y: 10 }
);

预期:

typescript
{
    type: "point",
    point: { x: 5, y: 5 }
}

二十、零长度线段问题 ​

20.1 什么是零长度线段? ​

如果:

A=B

那么:

r=B−A=(0,0)

因此:

r⋅r=0

线段退化为一个点。

20.2 为什么必须特殊处理? ​

普通求交公式:

t=q×sr×s

如果 r 是零向量:

r×s=0

但这并不能说明两条线段正常平行或共线。

同时,共线投影公式:

t0=q⋅rr⋅r

也会出现除零问题。

20.3 需要处理的情况 ​

ABCD处理方式
正常线段正常线段普通求交
零长度正常线段判断 A 是否在 CD 上
正常线段零长度判断 C 是否在 AB 上
零长度零长度判断 A、C 是否重合

二十一、实现 pointOnSegment() ​

21.1 函数目标 ​

判断点 P 是否位于有限线段 AB 上。

需要满足:

  1. P 与 AB 共线。
  2. P 位于 A、B 之间。
  3. 正确处理 A=B 的情况。

21.2 数学原理 ​

定义:

r=B−Aq=P−A

首先判断共线:

r×q=0

然后计算参数:

t=q⋅rr⋅r

最后判断:

0≤t≤1

21.3 TypeScript 实现 ​

typescript
function pointOnSegment(
    P: Vector2,
    A: Vector2,
    B: Vector2
): boolean {
    const r = subtractVector(B, A);
    const q = subtractVector(P, A);

    const rr = dotProduct(r, r);

    // AB 退化为点
    if (rr === 0) {
        return (
            P.x === A.x &&
            P.y === A.y
        );
    }

    // 判断是否共线
    if (crossProduct(r, q) !== 0) {
        return false;
    }

    // 计算投影参数
    const t = dotProduct(q, r) / rr;

    // 判断是否在线段范围内
    return t >= 0 && t <= 1;
}

21.4 测试 ​

typescript
const A = { x: 0, y: 0 };
const B = { x: 10, y: 0 };

console.log(
    pointOnSegment(
        { x: 5, y: 0 },
        A,
        B
    )
);

// true
typescript
console.log(
    pointOnSegment(
        { x: 15, y: 0 },
        A,
        B
    )
);

// false
typescript
console.log(
    pointOnSegment(
        { x: 5, y: 3 },
        A,
        B
    )
);

// false

二十二、实现完整 intersectSegments() ​

22.1 算法整体流程 ​

text
输入 A、B、C、D
        |
        v
计算 r、s、q
        |
        v
计算 rr、ss
        |
        v
判断零长度线段
        |
        +---- 两条都是点
        |          |
        |          v
        |       判断是否重合
        |
        +---- AB 是点
        |          |
        |          v
        |       pointOnSegment(A,C,D)
        |
        +---- CD 是点
        |          |
        |          v
        |       pointOnSegment(C,A,B)
        |
        v
计算 denominator = cross(r,s)
        |
        v
判断 denominator 是否为 0
        |
        +---- 是
        |      |
        |      v
        |   判断是否共线
        |      |
        |      +---- 否:none
        |      |
        |      +---- 是:共线区间求交
        |
        +---- 否
               |
               v
           计算 t、u
               |
               v
           判断 [0,1]
               |
               +---- 不满足:none
               |
               +---- 满足:point

22.2 TypeScript 完整实现 ​

typescript
function intersectSegments(
    A: Vector2,
    B: Vector2,
    C: Vector2,
    D: Vector2
): IntersectionResult {
    // 1. 计算方向向量
    const r = subtractVector(B, A);
    const s = subtractVector(D, C);
    const q = subtractVector(C, A);

    // 2. 计算长度平方
    const rr = dotProduct(r, r);
    const ss = dotProduct(s, s);

    // 3. 两条线段都退化为点
    if (rr === 0 && ss === 0) {
        if (
            A.x === C.x &&
            A.y === C.y
        ) {
            return {
                type: "point",
                point: A
            };
        }

        return { type: "none" };
    }

    // 4. AB 退化为点
    if (rr === 0) {
        return pointOnSegment(A, C, D)
            ? {
                type: "point",
                point: A
            }
            : {
                type: "none"
            };
    }

    // 5. CD 退化为点
    if (ss === 0) {
        return pointOnSegment(C, A, B)
            ? {
                type: "point",
                point: C
            }
            : {
                type: "none"
            };
    }

    // 6. 计算叉积
    const denominator = crossProduct(r, s);

    // 7. 平行情况
    if (denominator === 0) {
        // 平行但不共线
        if (crossProduct(q, r) !== 0) {
            return { type: "none" };
        }

        // 共线线段求交
        return intersectCollinearSegments(
            A,
            B,
            C,
            D
        );
    }

    // 8. 非平行:计算交点参数
    const t = crossProduct(q, s) / denominator;
    const u = crossProduct(q, r) / denominator;

    // 9. 判断交点是否位于有限线段
    if (
        t < 0 || t > 1 ||
        u < 0 || u > 1
    ) {
        return { type: "none" };
    }

    // 10. 计算交点
    return {
        type: "point",
        point: pointAt(A, B, t)
    };
}

二十三、完整测试用例 ​

测试 1:普通交叉 ​

typescript
intersectSegments(
    { x: 0, y: 0 },
    { x: 10, y: 10 },
    { x: 0, y: 10 },
    { x: 10, y: 0 }
);

预期:

typescript
{
    type: "point",
    point: { x: 5, y: 5 }
}

测试 2:平行不相交 ​

typescript
intersectSegments(
    { x: 0, y: 0 },
    { x: 10, y: 0 },
    { x: 5, y: 5 },
    { x: 15, y: 5 }
);

预期:

typescript
{ type: "none" }

测试 3:共线部分重叠 ​

typescript
intersectSegments(
    { x: 0, y: 0 },
    { x: 10, y: 10 },
    { x: 5, y: 5 },
    { x: 15, y: 15 }
);

预期:

typescript
{
    type: "overlap",
    start: { x: 5, y: 5 },
    end: { x: 10, y: 10 }
}

测试 4:共线完全分离 ​

typescript
intersectSegments(
    { x: 0, y: 0 },
    { x: 5, y: 5 },
    { x: 8, y: 8 },
    { x: 12, y: 12 }
);

预期:

typescript
{ type: "none" }

测试 5:端点接触 ​

typescript
intersectSegments(
    { x: 0, y: 0 },
    { x: 5, y: 5 },
    { x: 5, y: 5 },
    { x: 10, y: 10 }
);

预期:

typescript
{
    type: "point",
    point: { x: 5, y: 5 }
}

测试 6:反向重叠 ​

typescript
intersectSegments(
    { x: 0, y: 0 },
    { x: 10, y: 0 },
    { x: 8, y: 0 },
    { x: 2, y: 0 }
);

预期:

typescript
{
    type: "overlap",
    start: { x: 2, y: 0 },
    end: { x: 8, y: 0 }
}

测试 7:AB 退化为点且在线段上 ​

typescript
intersectSegments(
    { x: 5, y: 5 },
    { x: 5, y: 5 },
    { x: 0, y: 0 },
    { x: 10, y: 10 }
);

预期:

typescript
{
    type: "point",
    point: { x: 5, y: 5 }
}

测试 8:CD 退化为点且不在线段上 ​

typescript
intersectSegments(
    { x: 0, y: 0 },
    { x: 10, y: 0 },
    { x: 5, y: 5 },
    { x: 5, y: 5 }
);

预期:

typescript
{ type: "none" }

测试 9:两个相同的点 ​

typescript
intersectSegments(
    { x: 5, y: 5 },
    { x: 5, y: 5 },
    { x: 5, y: 5 },
    { x: 5, y: 5 }
);

预期:

typescript
{
    type: "point",
    point: { x: 5, y: 5 }
}

测试 10:两个不同的点 ​

typescript
intersectSegments(
    { x: 5, y: 5 },
    { x: 5, y: 5 },
    { x: 6, y: 5 },
    { x: 6, y: 5 }
);

预期:

typescript
{ type: "none" }

二十四、CAD 实际应用场景 ​

24.1 交点吸附(Intersection Snap) ​

当鼠标靠近两条线段交点时:

  1. 获取候选线段。
  2. 调用 intersectSegments()。
  3. 判断返回类型。
  4. 获取交点坐标。
  5. 计算交点与鼠标的屏幕距离。
  6. 如果距离小于吸附容差,则显示吸附标记。

24.2 线段修剪(Trim) ​

例如:

text
A ---------------- B
          |
          |
          C
          |
          D

如果需要以 CD 为边界修剪 AB:

  1. 计算 AB 与 CD 所在直线或线段的交点。
  2. 判断交点是否满足修剪工具的规则。
  3. 根据鼠标选择的保留侧,更新 AB 的端点。

注意:

完整 Trim 工具可能需要直线延长、边界选择和多候选交点处理,不能仅依赖有限线段求交。

24.3 线段延长(Extend) ​

Extend 通常需要计算:

  • 线段所在直线与目标边界的交点。
  • 交点是否位于允许的延长方向。
  • 哪个端点需要延长。

24.4 多边形边界检测 ​

多边形由多个线段组成。

判断两条多边形边界是否相交时,可以逐对检测边。

24.5 图形布尔运算 ​

例如:

  • Union(并集)。
  • Intersection(交集)。
  • Difference(差集)。

线段求交是二维布尔运算的重要基础。

但完整布尔运算还需要:

  • 多边形拓扑关系。
  • 交点排序。
  • 边界分割。
  • 内外关系判断。
  • 数值稳健性处理。

二十五、Day 10 常见错误 ​

错误 1:叉积为零就认为不相交 ​

错误:

typescript
if (denominator === 0) {
    return { type: "none" };
}

因为两条线段可能共线并重叠。

正确做法:

继续判断是否共线。

错误 2:平行等于共线 ​

错误。

需要判断:

r×s=0

以及:

q×r=0

错误 3:共线等于重叠 ​

错误。

共线线段可能完全分离。

需要进一步计算参数区间交集。

错误 4:只判断 t,不判断 u ​

错误。

交点必须同时位于两条有限线段上。

因此:

0≤t≤1

并且:

0≤u≤1

错误 5:没有处理反向线段 ​

例如:

C=(8,0)D=(2,0)

如果默认:

t0<t1

可能得到错误的重叠区间。

正确做法:

typescript
Math.min(t0, t1)
Math.max(t0, t1)

错误 6:忽略零长度线段 ​

如果:

A=B

那么:

r=(0,0)

普通求交公式可能失效。

必须先处理退化情况。

错误 7:浮点数直接比较 ​

例如:

typescript
denominator === 0

对于整数坐标和简单测试数据通常容易理解。

但在实际 CAD 中,浮点计算可能存在误差。

例如理论上应该为零的叉积,计算结果可能是:

typescript
1.4210854715202004e-14

不过,不能简单地将所有比较替换为:

typescript
Math.abs(cross) < 1e-10

因为叉积的量纲是长度平方,结果会受到坐标尺度影响。

后续工程实践中,需要学习:

  • 相对容差。
  • 尺度相关容差。
  • 稳健方向谓词。
  • 近似共线与精确共线的区别。
  • 浮点数误差传播。

二十六、Day 10 练习题 ​

练习 1:二维叉积 ​

已知:

a=(3,2)b=(1,4)

求:

a×b

并判断从 a 到 b 的旋转方向。

练习 2:平行判断 ​

已知:

A=(0,0)B=(10,10)C=(0,5)D=(10,15)

判断两条直线是否平行。

练习 3:共线判断 ​

已知:

A=(0,0)B=(10,10)C=(5,5)D=(15,15)

判断:

  1. 是否平行?
  2. 是否共线?
  3. 是否重叠?

练习 4:普通线段求交 ​

已知:

A=(0,0)B=(10,10)C=(0,10)D=(10,0)

求:

  1. r。
  2. s。
  3. q。
  4. 分母 r×s。
  5. 参数 t。
  6. 参数 u。
  7. 交点坐标。

练习 5:共线重叠 ​

已知:

A=(0,0)B=(10,0)C=(3,0)D=(15,0)

求:

  1. t0。
  2. t1。
  3. startT。
  4. endT。
  5. 重叠线段端点。

练习 6:反向线段 ​

已知:

A=(0,0)B=(10,0)C=(8,0)D=(2,0)

求重叠区间。

练习 7:零长度线段 ​

已知:

A=(5,5)B=(5,5)C=(0,0)D=(10,10)

判断两条线段是否相交。

练习 8:TypeScript 综合题 ​

独立实现:

typescript
function intersectSegments(
    A: Vector2,
    B: Vector2,
    C: Vector2,
    D: Vector2
): IntersectionResult {
    // TODO
}

要求:

  1. 普通相交。
  2. 平行不相交。
  3. 共线重叠。
  4. 共线分离。
  5. 端点接触。
  6. 反向重叠。
  7. 零长度线段。
  8. 两个点重合。
  9. 两个点不重合。

二十七、Day 10 核心公式汇总 ​

知识点核心公式
向量减法AB=B−A
点积a⋅b=axbx+ayby
二维叉积a×b=axby−aybx
叉积与夹角$a\times b=
平行判断r×s=0
共线判断r×s=0, q×r=0
参数方程P(t)=A+t(B−A)
交点参数 tt=q×sr×s
交点参数 uu=q×rr×s
有限线段判断0≤t≤1, 0≤u≤1
交点坐标P=A+tr
共线投影 t0t0=(C−A)⋅rr⋅r
共线投影 t1t1=(D−A)⋅rr⋅r
重叠起点startT=max(0,min(t0,t1))
重叠终点endT=min(1,max(t0,t1))

二十八、Day 10 最终验收清单 ​

数学基础 ​

  • [ ] 理解二维叉积。
  • [ ] 能手算二维叉积。
  • [ ] 能根据叉积判断方向。
  • [ ] 理解叉积与面积的关系。
  • [ ] 能判断两条直线是否平行。
  • [ ] 能判断两条直线是否共线。
  • [ ] 理解线段参数方程。
  • [ ] 能推导交点参数 t、u。
  • [ ] 能判断交点是否位于有限线段内。
  • [ ] 能计算共线线段的重叠区间。

TypeScript ​

  • [ ] 实现 crossProduct()。
  • [ ] 实现 orientation()。
  • [ ] 实现 areParallel()。
  • [ ] 实现 areCollinear()。
  • [ ] 实现 pointAt()。
  • [ ] 实现 pointOnSegment()。
  • [ ] 实现 intersectCollinearSegments()。
  • [ ] 实现 intersectSegments()。
  • [ ] 能通过全部测试用例。

CAD 应用 ​

  • [ ] 能计算两条线段的交点。
  • [ ] 能实现基础交点吸附。
  • [ ] 理解线段修剪的几何基础。
  • [ ] 理解线段延长的几何基础。
  • [ ] 能判断共线线段是否重叠。
  • [ ] 能处理端点接触。
  • [ ] 能处理零长度线段。
  • [ ] 理解线段求交与多边形算法的关系。
  • [ ] 理解浮点误差对几何计算的影响。

二十九、Day 10 知识总结 ​

本节最重要的三个知识点:

1. 叉积可以判断方向、平行和共线 ​

a×b=axby−aybx

二维叉积是计算几何中非常重要的基础工具。

2. 参数方程可以将几何求交转换为代数问题 ​

两条直线:

P(t)=A+trQ(u)=C+us

相交时:

A+tr=C+us

通过叉积得到:

t=q×sr×su=q×rr×s

然后判断:

0≤t,u≤1

即可确定有限线段是否相交。

3. 共线重叠可以转换为一维区间求交 ​

将 CD 的两个端点投影到 AB 的参数轴上:

t0, t1

然后计算:

startT=max(0,min(t0,t1))endT=min(1,max(t0,t1))

根据 startT 和 endT 的大小关系,判断:

  • 不相交。
  • 单点接触。
  • 线段重叠。

三十、Day 06–Day 10 阶段知识联系 ​

text
Day 06:矩阵基础
    |
    ├── 矩阵结构
    ├── 矩阵乘法
    └── 单位矩阵
    |
    v
Day 07:二维仿射变换
    |
    ├── 缩放
    ├── 旋转
    ├── 平移
    ├── 齐次坐标
    └── 组合变换
    |
    v
Day 08:逆矩阵与坐标转换
    |
    ├── 行列式
    ├── 逆矩阵
    ├── worldToScreen
    └── screenToWorld
    |
    v
Day 09:点到线段距离
    |
    ├── 向量投影
    ├── Clamp
    ├── 最近点
    ├── 最短距离
    └── hitTestSegment
    |
    v
Day 10:线段求交
    |
    ├── 二维叉积
    ├── 平行判断
    ├── 共线判断
    ├── 参数方程
    ├── 交点计算
    ├── 重叠区间
    └── 零长度线段

五天的核心数学工具 ​

数学工具主要作用CAD 应用
矩阵坐标变换平移、旋转、缩放
逆矩阵撤销坐标变换屏幕转世界坐标
点积投影与距离拾取、最近点吸附
叉积方向与相交关系交点吸附、线段求交
参数方程表示线段上的位置求交、裁剪、修剪
区间求交计算重叠范围共线重叠检测

Day 10 核心结论:

点积主要解决投影与距离问题。

叉积主要解决方向、平行、共线和相交问题。

参数方程将二维几何问题转换为代数问题。

通过叉积、点积、参数方程和区间求交,可以实现一个能够处理普通相交、共线重叠、端点接触和零长度线段的二维线段求交算法。


当前学习进度:Day 10 完成。

Day 06–Day 10 阶段复习整理完成。

下一阶段:Day 11——点与多边形的位置关系(Point in Polygon)。